#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
	int data;
	struct tree *left;
	struct tree *right;
}btree;

int badd(btree **root,int data)
{
	if((*root)==NULL)
	{
		btree *temp=(btree *)malloc(sizeof(btree));
		(*root)=temp;
		(*root)->data=data;
		(*root)->left=NULL;
		(*root)->right=NULL;
	}
	else
	{
		if(data<(*root)->data)	badd(&(*root)->left,data);
		if(data>(*root)->data)  badd(&(*root)->right,data);
	}

}

btree *bst(btree **root,int data)
{
	if((*root)==NULL) 
	{
		printf("number not found \n");
		return NULL;
	}
	if((*root)->data==data) return (*root);
	if(data>(*root)->data) return bst(&(*root)->right,data);
	if(data<(*root)->data) return bst(&(*root)->left,data);

}

int bfree(btree **root)
{
	if((*root)==NULL) return 0;
	btree *temp;
	temp=(*root);
	bfree(&(*root)->left);
	bfree(&(*root)->right);
	free(temp);
}
int binorder(btree **root)
{
	if((*root)==NULL) return 0;
	binorder(&(*root)->left);
	printf("%d ",(*root)->data);
	binorder(&(*root)->right);
}

int bpreorder(btree **root)
{
	if((*root)==NULL) return 0;
	printf("%d ",(*root)->data);
	bpreorder(&(*root)->left);
	bpreorder(&(*root)->right);
}

int bpostorder(btree **root)
{
	if((*root)==NULL) return 0;
	bpostorder(&(*root)->left);
	bpostorder(&(*root)->right);
	printf("%d ",(*root)->data);
}

struct queue
{
	int head;
	int top;
	btree *items[20];
};
int enqueue(struct queue *q,btree *data)
{
	q->items[q->top]=data;
	if(q->top==20)
	{
		q->top=1;
	}
	else
	{
		q->top++;
	}
}

btree *dequeue(struct queue *q)
{
	btree *x=q->items[q->head];
	if(q->head==q->top) return NULL;
	if(q->head==20)
	{
		q->head=1;
	}
	else
	{
		q->head+=1;
	}
	return x;
}

int blevelorder(btree **root)
{
	struct queue *q;
	q=(struct queue *)malloc(sizeof(struct queue));
	btree *temp=(*root);
	if((*root)==NULL) return 0;
	while(temp)
	{
		printf("%d ",temp->data);
		if(temp->left) enqueue(q,temp->left);
		if(temp->right) enqueue(q,temp->right);
		temp=dequeue(q);
	}
	free(q);
}


int bheight(btree **root)
{
	int hl,h,hr;
	hl=h=hr=0;
	if((*root)==NULL) return 0;
	hl=(1+bheight(&(*root)->left));
	hr=(1+bheight(&(*root)->right));
	h=hl>hr?hl:hr;
	return h;
}

btree *bstsuc(btree **root,btree *node)
{
	btree *tmp=NULL;
	btree *temp=(*root);
	if(node->right!=NULL)
	{
		tmp=node->right;
		while(tmp->left!=NULL) tmp=tmp->left;
		return tmp;
	}
	else
	{
		while(temp!=NULL)
		{
			if(node->data<temp->data)
			{
				tmp=temp;
				temp=temp->left;
			}
			if(node->data>=temp->data) return tmp;
		}
	}
}

//int bdelete(btree **root,btree *node)
//{
//	if(



int main()
{
	btree *root=NULL;
	btree *tmp=NULL;
	badd(&root,7);
	badd(&root,9);
	badd(&root,8);
	badd(&root,4);
	badd(&root,3);
	badd(&root,5);
	printf("\n");
	tmp=bst(&root,3);
	if(tmp!=NULL) printf("\nsearched number found = %d \n",tmp->data);
	tmp=bstsuc(&root,tmp);
	printf("successor is 5 %d \n",tmp->data);
	printf("root value is %d\n",root->data);
	binorder(&root);
	bpreorder(&root);
	bpostorder(&root);
	printf("height of tree : %d \n",bheight(&root));
	blevelorder(&root);
	bfree(&root);
	return 0;
}
